package Leetcode第二期;

import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * @author : K k
 * @date : 10:15 2020/9/29
 */
public class 二叉树的后序遍历_145 {
    List<Integer> res=new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        post(root);
        return res;
    }
    //思路： 递归
    private void post(TreeNode root) {
        if (root==null){
            return;
        }
        post(root.left);
        post(root.right);
        res.add(root.val);
    }

    //迭代
    public List<Integer> postorderTraversalA(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if (root==null){
            return res;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.left!=null){
                stack.push(node.left);
            }
            if (node.right!=null){
                stack.push(node.right);
            }
            res.add(0,node.val);
        }
        return res;
    }
}
